from tree_node import TreeNode

class Solution:
    """
    该方法实现的前提是：预期p和q必定存在于root之下，即必定有公共祖先
    例如：
    1
    2       3
    4   5   6   7
    整体逻辑还是比较抽象的。
    """
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        # 如果根节点不存在，则直接返回上级重新找
        if not root:
            return None
        # 如果当前树的根节点，是p或者q，也直接返回
        # 两种可能性：1. root就是pq的公共祖先；2. root只是某一个节点的情况（非公共祖先）
        if root == p or root == q: 
            return root
        # 查找左子树的公共祖先
        # 对应上面3种情况：
        # 1. 返回非空节点，且是pq的公共祖先。此种情况，另一子树返回的结果必定是空。因此返回当前子树节点
        # 2. 返回非空节点，且仅是pq的某一节点。此种情况，另一子树，必定也会返回非空节点。此种情况，当前父节点才是真实的公共祖先
        # 3. 返回空节点
        # 3.1. 另一子树，返回空。则说明当前根节点内根本没有pq两个节点。返回空，相当于告诉父级：这里什么都没有。
        # 3.2. 另一子树，返回非空。参考情况1和2
        left = self.lowestCommonAncestor(root.left, p, q)
        # 查找右子树的公共祖先
        right = self.lowestCommonAncestor(root.right, p, q)
        # 如果左子树的公共祖先不存在，则返回右侧
        if not left: 
            return right
        if not right: 
            return left
        return root
